package Testdemo3.Test1;

import  java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-05-10
 * Time：14:17
 */




public class Test1 {

    /**
     * 一维数组的前缀和
     * 利用动态规划思想
     * 先利用一个 dp 统计 该位置 到 0 位置的的 和
     * 然后进行差值转化成某段区间的
     */


    public static void main2(String[] args) {


        // 创建句柄
        Scanner in = new Scanner(System.in);


        // 数组长度
        int n=in.nextInt();

        // 查询次数
        int q=in.nextInt();


        // 有可能长度 过大造成越界
        // 所以我们用 long
        long [] array=new long [n+1];


        // 输入数组
        // 我们输入的是 从 1 位置 开始进行 输入
        for(int i =1 ; i < n+1 ; ++i) {

            array[i]=in.nextInt();

        }

        int k=0;

        long[] dp=new long[n+1];
        dp[0]=0;

        /**
         *          这里统计的时候
         *          我们也通过 1 位置开始进行统计
         *          防止特殊情况的发生
         *          对于 0 左边的值 默认是可以为 0
         *          一旦为 需要判断 1 左边的元素时
         *          我们就可以 空一个元素来判断
         *
         */


        for(int x= 1; x < n+1 ; x++ ) {
            dp[x]= dp[x-1] + array[x];
        }


        // 进行查询
        while(q != 0) {

            // 左边值
            int left = in.nextInt();

            int right = in.nextInt();

            // 每查询一个打印一个
            System.out.println(dp[right]-dp[left-1]);


            k++;

            q--;

        }





    }




    public static void main1(String[] args) {


        Scanner in = new Scanner(System.in);
        int [] array=new int [100000];

        int n=in.nextInt();
        int q=in.nextInt();

        for(int i =0 ; i < n ; ++i) {

            array[i]=in.nextInt();

        }

        int k=0;

        int[] sum=new int[q];

        while(q != 0) {

            int left=in.nextInt();

            int right=in.nextInt();

            for(int j = left-1 ;  j < right ; ++j) {
                sum[k] += array[j];
            }

            k++;

            q--;
        }


        for(int i=0; i< sum.length; ++i) {

            System.out.println(sum[i]);

        }

    }

    /**
     * 二维数组的前缀和
     * 本质上还是利用了一维数组的 动态规划思想 进行累加 即可
     *
     */

    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        long array[][] = new long[n + 1][m + 1];


        for (int i = 1; i < n + 1; ++i) {
            for (int j = 1; j < m + 1; j++) {
                array[i][j] = in.nextInt();
            }
        }

        /**
         * 这里需要 放置 足够大的类型
         * 所以我们用 long
         */

        long dp[][] = new long[n + 1][m + 1];

        // 统计每行的 前数字和
        for (int i = 1; i < n + 1; ++i) {
            for (int j = 1; j < m + 1; j++) {
                dp[i][j]=dp[i][j-1] + array[i][j];
            }
        }


        while(q > 0) {
            int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();

            long sum=0;

            // 进行每行 有效区域 的累加
            for(int k= x1 ; k <= x2 ; k++) {

                sum += ( dp[k][y2]- dp[k][y1-1] );
            }

            // 最终的 总和就是我们需要的 左上角 (x1,y1)
            // 和 右下角 (x2,y2) 所围成的矩阵区域的总和

            System.out.println(sum);


            q--;
        }

    }


    /**
     * 方法二 ： 利用 区域和 来塑造一个二维数组的 动态规划图
     *  当我们需要求一段区域时
     *  A   B
     *  C   D
     *  全部区域可以 分解 为 (A + B) + (A + C) + D - A
     *
     *  得到部分区域 可以理解为 (A+B+C+D) - (A + B) - (C+A) + A
     */

    public static void main8(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        long array[][] = new long[n + 1][m + 1];


        // 输入数据
        for (int i = 1; i < n + 1; ++i) {
            for (int j = 1; j < m + 1; j++) {
                array[i][j] = in.nextInt();
            }
        }

        // 建立 一个 dp 数组
        long dp[][] = new long[n + 1][m + 1];
        for (int i = 1; i < n + 1; ++i) {
            for (int j = 1; j < m + 1; j++) {
                // 用区域 a + b + c - d 来确定 不同边界值之间的总和
                // 以此来计算我们面积 总和
                dp[i][j]= dp[i][j-1] + dp[i-1][j] + array[i][j] - dp[i-1][j-1];
            }
        }


        while(q > 0) {
            int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();

            // 总的面积 - b - c + a
            // 最终得到我们 d 的面积
            long sum= dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];

            System.out.println(sum);


            q--;
        }

    }

    /**
     * 寻找数组的中心下标
     *
     *
     * 方法 一 :
     * 利用动态规划思想 统计
     * 前 i -1 项的和 放入 dp 数组内
     * 然后进行 差值 得到想要的 某段子数组的 总和
     */


    public static void main5(String[] args) {
        int[] nums= new int[]{1,7,3,6,5,6};
        System.out.println(pivotIndex(nums));
    }

    public static int pivotIndex(int[] nums) {

        // 得到长度
        int n= nums.length;
        int []dp= new int[n+1];



        // 统计 前 i-1 项的和
        // 但注意 这里 原数组 0 位置 是有数据的
        for(int i=1; i < n+1; ++i) {
            dp[i]= dp[i-1]+ nums[i-1];
        }



        for(int k=1; k < n-1 ; k++) {

            // 只要 前 k-1 项的和 等于 k+1 到 数组右边界 值
            if(dp[k-1] == (dp[n]- dp[k])) return k-1;
        }

        /**
         * 左边界可以为 0
         * 但右边界 不能为 0
         */

        // 如果未找到就返回 -1
        return -1;
    }


    /**
     * 寻找数组的中心下标
     *
     * 我们分别用 前缀和 与 后缀和 的方式
     * 来直接进行比较
     *
     */


    public int pivotIndex2(int[] nums) {

        // 得到 数组长度
        int n= nums.length;


        // 定义 一个前缀和的数组
        int [] dpleft= new  int[n+1];

        // 得到前缀和 数组
        for(int i= 1; i< n ; ++i) {
            dpleft[i] = dpleft[i-1] + nums[i-1];
        }


        // 定义一个后缀和的数组
        int [] dpright =  new int[n+1];

        // 得到后缀和数组
        for(int j = n -1 ; j  >= 0 ; j--) {
            dpright[j] = dpright[j+1] + nums[j];
        }

        // 开始遍历寻找中间值
        for(int k= 0 ; k < n ; k++) {
            if(dpleft[k] == dpright[k+1]) {
                return k;
            }

        }

        return -1;

    }



    /**
     * 除自身 以外数组的乘积
     *
     * 方法 ：  利用 前缀积 和 后缀积 数组进行 相乘
     *
     * @param nums 目标数组
     * @return 返回一个 整型数组
     *
     */



    public int[] productExceptSelf(int[] nums) {

        // 得到数组长度
        int n= nums.length;


        // 定义一个前缀积的数组
        int[] dpleft = new int [n+1];
        dpleft[0]= 1;

        // 进行前缀积
        for(int i =1 ; i < n+1 ; ++i) {
            dpleft[i]=nums[i-1] * dpleft[i-1];
        }


        // 定义 一个后缀积的数组
        int[] dpright= new int[n+1];
        dpright[n]=1;

        // 进行后缀积的数组
        for(int  j = n-1 ; j >= 0; j-- ) {
            dpright[j]= nums[j] * dpright[j+1];
        }

        int[] ret= new int[n];

        // 得到返回值
        for(int i =0 ; i < n; ++i) {
            ret[i]= dpleft[i] * dpright[i+1];
        }


        return ret;
    }


    public static void main10(String[] args) {
        int [] array= new int[]{-1,-1,1};
        System.out.println(subarraySum(array, 1));
    }

    public static int subarraySum(int[] nums, int k) {
        int n= nums.length;

        int[] dp= new int[n+1];

        // 初始化 dp 数组
        for(int i = 1 ; i < n+1 ; ++i) {
            dp[i] = dp[i-1] + nums[i-1];
        }


        int count=0;


       for (int i=0; i< n+1;++i) {
           for (int j=i+1; j< n+1; ++j) {
               if (dp[j]-dp[i]==k) {
                   count++;
               }
           }
       }

        return count;



    }


    public static void main7(String[] args) {
        int[]array={1,1,2};
        System.out.println(subarraySum2(array, 2));
    }
    public static int subarraySum2(int[] nums, int k) {
        Map<Integer,Integer> map= new HashMap<>();

        map.put(0,1);
        int ret=0, sum=0;
        for(int i=0; i< nums.length; ++i) {
            sum += nums[i];
            ret += map.getOrDefault(sum-k,0);
            map.put(sum, map.getOrDefault(sum,0)+1);
        }

        return ret;
    }



    public int subarraysDivByK(int[] nums, int k) {
        Map<Boolean, Integer> map= new HashMap<>();
        int n= nums.length;
        int ret=0,sum=0;


        for(int i=0; i < n; ++i ) {
            sum += nums[i];
            ret += map.getOrDefault(sum % k == 0,0);
            map.put(true,map.getOrDefault(sum,0)+1);
        }

        return ret;
    }


    /**
     *  能被 k 整除 的子数组
     *
     *  前缀和 + 哈希表
     *  <1> 余值定理
     *   (a-b) % k = 0 ===> a % k = b % k
     *   <2> java 取模 的值出现 负数的情况
     *   ( ( a % k + k ) % k (所以情况下) )  =  ( a % k (整数情况下) )
     * @param nums 目标数组
     * @param k 用来取模的 k 值
     * @return 返回 子数组 中 能被 k 整除的 子数组 的个数
     *
     */

    public int subarraysDivByK2(int[] nums, int k) {

        // 定义 一个哈希表
        Map<Integer, Integer> map= new HashMap<>();
        int n= nums.length;
        int ret=0,sum=0;

        // 可以理解为 从 0 位置放入 0 数据
        map.put(0/k,1);

        for(int i=0; i < n; ++i ) {


            sum += nums[i];

            // 除去 Java 中 取模是 负数的情况
            int r=  (sum % k + k) % k  ;

            // 通过 余值定理 可知
            // sum % k =   a  % k
            // 这里就可以转化成 前面 【0, i-1】的位置
            // 是否存在 哈希表中
            ret += map.getOrDefault(r,0);

            // 将前缀和数据放入 哈希表中
            map.put(r,map.getOrDefault(r,0)+1);
        }

        return ret;
    }

    /**
     *
     *
     * 和为 k 的子数组
     *
     * 利用 前缀和 + 哈希表
     * @param nums 目标数组
     * @param k 目标和
     * @return 返回子数组 和为 k 的子数组的个数
     *
     */

    public int subarraySum3(int[] nums, int k) {

        Map<Integer,Integer> map= new HashMap<>();

        // 定义初始0 位置的前缀和 为 0
        map.put(0,1);

        int ret=0, sum=0;

        for(int i=0; i< nums.length; ++i) {
            // 前缀和
            sum += nums[i];

            // 更新结果
            ret += map.getOrDefault(sum-k,0);

            // 放入前缀和到哈希表
            map.put(sum, map.getOrDefault(sum,0)+1);
        }

        return ret;
    }
}
